Numerous conventional authentication systems make use of distributed cryptography arrangements. For example, in a typical distributed cryptography arrangement, a secret value is stored in a distributed manner across multiple servers instead of being stored in its entirety on a single server, as a basic defense against compromise of the single server. Efficient distributed cryptographic protocols are known for use in these and other settings, including protocols for operations such as digital signing, key generation, encryption and decryption.
Most of these known distributed cryptographic protocols rely on homomorphic properties inherent in public-key cryptographic primitives, which generally allow partial operations executed with individual key shares to be combined to achieve an operation with a complete private key.
However, many authentication systems require verification of secret values that are constructed using symmetric-key primitives. These include, for example, password-based Kerberos authentication and one-time passcode authentication. Efficient execution of standard symmetric-key primitives typically requires that at least one server or other participating distributed entity have full knowledge of the corresponding key. For example, to encrypt a message m under symmetric key κ using the Advanced Encryption Standard (AES), a participating distributed entity must know both κ and m. Accordingly, verification of a secret value derived using symmetric-key operations would appear to expose one or more of the distributed entities to potential compromise.
Although fully distributed verification of a secret value based purely on symmetric-key operations is possible using security multiparty computation techniques, these techniques require excessive bandwidth and computational resources.